package hihocode;

import java.util.Scanner;

//最长回文子串
public class LongestPalindromeSubstring {

	// 令f[i] 表示以第i个字符为中心的最长回文子串的长度
	// 通过使得右边界（j + f(j) / 2）最大的那个j来辅助计算才是，
	// 所以公式将变成 f(i) ≥ min{f(2*j-i) , f(j) -2*(i-j)}这种形式了！

	// 统计使得回文串右边界（j + f(j) / 2）最大的那个j，
	// 然后再计算每一个i的时候，都可以通过f(i)≥ min⁡{f(2*j-i), f(j)-2*(i-j)}这个公式来知道f(i)的一个最小值

	// ===========================================
	// Manacher算法, Time: O(N), Space: O(N)
	// http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
	public static int longestPalindromeManacher(String s) {
		String T = preProcess(s);
		int len = T.length(); // 经过变化后，len总是为奇数长
		
		// P数组存放在以index为中心的回文半径长度
		int[] radius = new int[len];
		int C = 0, R = 0; // C为最长回文子串的中心位置，R为当前最长回文子串的右边界位置
		// 第0个字符和最后一个字符是无效字符，仅为了避免边界检查
		for (int i = 1; i < len - 1; i++) {
			// 计算i以C为中心的对应回文左边匹配位置
			//C 等于上一轮的j
			int iMirror = 2 * C - i;

			// R > i 表示i...R是回文串的右半部分
			//初始iMirror为-1，但是此时R < i
			//R为f(j) / 2 + C
			//那这个为什么不是f(j) + 2 * C - 2 * i呢，因为这儿存储的是半径，所以长度为 原有的 / 2
			radius[i] = (R > i) ? Math.min(R - i, radius[iMirror]) : 0;

			// 贪心拓展以i为回文中心的回文子串
			while (T.charAt(i + radius[i] + 1) == T.charAt(i - radius[i] - 1)) {
				radius[i]++;
			}

			// 如果以i为中心的回文扩展超过了R，则我们找到一个新的更长回文子串
			// 因此 更新 最长回文子串的中心和右边界
			if (radius[i] > R - i) {
				C = i;
				R = i + radius[i];
			}
		}

		// 现在P[i]数组里存放了以i为中心的回文子串长度，用打擂台方式找到最长者
		int maxLen = 0;
		for (int i = 1; i < len - 1; i++) {
//			System.out.println(radius[i]);
			if (radius[i] > maxLen) {
				maxLen = radius[i];
			}
		}
		return maxLen;
	}

	public static int longestPalindromeManacher2(String s) {
		String T = preProcess(s);
		int len = T.length(); // 经过变化后，len总是为奇数长
		
		// P数组存放在以index为中心的回文子串长度
		int[] length = new int[len];
		int C = 0, R = 0; // C为最长回文子串的中心位置，R为当前最长回文子串的右边界位置
		// 第0个字符和最后一个字符是无效字符，仅为了避免边界检查
		for (int i = 1; i < len - 1; i++) {
			// 计算i以C为中心的对应回文左边匹配位置
			//C 等于上一轮的j
			int iMirror = 2 * C - i;

			// R > i 表示i...R是回文串的右半部分
			//初始iMirror为-1，但是此时R < i
			//R为f(j) / 2 + C
			//那这个为什么不是f(j) + 2 * C - 2 * i呢，因为这儿存储的是半径，所以长度为 原有的 / 2
			
			//这里为什么初始化为0呢？初始化为1会怎样
			//就应该初始化为1，因为对于长度而言，初始即为1
			length[i] = (R > i) ? Math.min(2 * R + 1 - 2 * i, length[iMirror]) : 1;

			// 贪心拓展以i为回文中心的回文子串
			while (T.charAt(i + length[i] / 2 + 1) == T.charAt(i - length[i] / 2 - 1)) {
				length[i] += 2;
			}

			// 如果以i为中心的回文扩展超过了R，则我们找到一个新的更长回文子串
			// 因此 更新 最长回文子串的中心和右边界
			if (length[i] / 2 > R - i) {
				C = i;
				R = i + length[i] / 2;
			}
		}

		// 现在P[i]数组里存放了以i为中心的回文子串长度，用打擂台方式找到最长者
		int maxLen = 0;
		for (int i = 1; i < len - 1; i++) {
//			System.out.println(radius[i]);
			if (length[i] > maxLen) {
				maxLen = length[i];
			}
		}
		return maxLen / 2;
	}
	
	// 把s转换成T，如s="abba"，则T="^#a#b#b#a#$"
	// ^和$加在字符串首尾用来避免边界检查
	private static String preProcess(String s) {
		int len = s.length();
		if (len == 0) {
			return "^$";
		}
		StringBuilder ret = new StringBuilder(2 * len + 3);
		ret.append("^");
		for (int i = 0; i < len; i++) {
			ret.append('#').append(s.charAt(i));
		}
		ret.append("#$");
		return ret.toString();
	}

	public static void main(String[] args) {
		int num;
		Scanner scanner = new Scanner(System.in);
		num = scanner.nextInt();
		int res = 0;
		scanner.nextLine();
		for (int i = 0; i < num; i++) {
			res = longestPalindromeManacher2(scanner.nextLine());
			System.out.println(res);
		}
		scanner.close();
	}

	// public static void main(String[] args) {
	// Scanner scanner = new Scanner(System.in);
	// int testCase = scanner.nextInt();
	// scanner.nextLine();
	// String source = "";
	// String reverse = "";
	// for(int i = 0; i <= testCase; i++){
	// source = scanner.nextLine();
	// reverse = new StringBuilder(source).reverse().toString();
	// System.out.println(getLongest(source, reverse));
	//
	// }
	// scanner.close();
	// }

	// 最长公共子串的长度

	// 这个TLE了
	// 思路也是错的
	// 比如"abcdasdfghjkldcba", 是用来求最长回文子序列的
	public static int getLongest(String S, String T) {
		if (S == null || T == null) {
			return -1;
		}
		if (S.length() <= 0 || T.length() <= 0) {
			return 0;
		}
		int max = -1;
		int[][] result = new int[S.length() + 1][T.length() + 1];
		for (int i = 1; i < result.length; i++) {
			for (int j = 1; j < result[0].length; j++) {
				if (S.charAt(i - 1) == T.charAt(j - 1)) {
					result[i][j] = result[i - 1][j - 1] + 1;
				} else {
					result[i][j] = 0;
				}
				if (result[i][j] > max) {
					max = result[i][j];
				}
			}
		}
		return max;
	}
}
